| Everything原理及个人实现 | 您所在的位置：网站首页 › 源代码 everything is gonna be ok › Everything原理及个人实现 |
Everything原理及个人实现
|
Everything原理及实现
网上找了很多的资料，还是没有很清楚的了解Everything这款软件。所以自己研究了以下，并记录下来。 Everything是一个搜索文件速度超快的软件，相比Windows自带的搜索功能，Everything可以做到在数十万文件中做到秒搜。 本文来分析一下Everything背后的原理以及自己实现一个Everything。 Everything的工作原理Everything在第一次打开程序时会扫描整个磁盘，并建立一个索引库。需要注意的是，Everything并不是像Windows文件夹遍历那样一个文件一个文件的搜索并记录。而是通过NTFS文件系统的特性，MFT和USN journal。这也是Everything仅支持NTFS文件系统的原因。 Master File Table (MTF) 在NTFS文件系统中，有一个特殊的表，称为MTF表。所有文件夹和文件的名称都被存储在该表中，Everything通过遍历这个表的所有内容，实现在不遍历文件系统就能获取当前磁盘中的所有文件的名称和路径。 USN journal NTFS的日志功能。所有对文件系统的修改操作都被记录在了一个journal日志文件中。Everything通过监控这个日志文件实现对文件修改的监控。 文件查找 通过字符串匹配算法从之前建立的索引中对字符串进行匹配，并显示文件名称和路径。 自己实现一个Everything我自己已经实现了一个完整的类似于Everything的软件，代码已经在GitHub上开源，欢迎各位去点个star呀。 XUANXUQAQ/File-Engine: An app launcher && efficiency tool (github.com) 一、建立数据库索引首先，我们需要做的就是对文件的路径进行索引。我这里选用SQLite。不知道Everything是使用了什么数据库才使他们的索引文件做到这么小，至于为什么这么快，推测可能是先将索引放入内存，索引可用后，程序在后台慢慢同步到硬盘的吧。 搜索的核心方法是通过创建USN日志并进行读取，然后将数据还原成文件路径并写入数据库。 1. 首先是获取驱动盘的句柄 通过CreateFile方法打开磁盘，并返回磁盘句柄。 关于CreateFile的用法详见MSDNCreateFileW function (fileapi.h) - Win32 apps | Microsoft Docs inline bool volume::getHandle() { // 为\\.\C:的形式 CString lpFileName(_T("\\\\.\\c:")); lpFileName.SetAt(4, vol); hVol = CreateFile(lpFileName, GENERIC_READ | GENERIC_WRITE, // 可以为0 FILE_SHARE_READ | FILE_SHARE_WRITE, // 必须包含有FILE_SHARE_WRITE nullptr, OPEN_EXISTING, // 必须包含OPEN_EXISTING, CREATE_ALWAYS可能会导致错误 FILE_ATTRIBUTE_READONLY, // FILE_ATTRIBUTE_NORMAL可能会导致错误 nullptr); if (INVALID_HANDLE_VALUE != hVol) { return true; } return false; }2. 之后开始创建USN日志 通过DeviceIoControl方法向磁盘发送FSCTL_CREATE_USN_JOURNAL命令，创建USN日志。 关于DeviceIoControl的用法，详见MSDNDeviceIoControl function (ioapiset.h) - Win32 apps | Microsoft Docs DeviceIoControl的各个命令操作，详见MSDNVolume Management Control Codes - Win32 apps | Microsoft Docs 这里创建USN日志使用的是FSCTL_CREATE_USN命令FSCTL_CREATE_USN_JOURNAL - Win32 apps | Microsoft Docs inline bool volume::createUSN() { cujd.MaximumSize = 0; // 0表示使用默认值 cujd.AllocationDelta = 0; // 0表示使用默认值 DWORD br; if ( DeviceIoControl(hVol, // handle to volume FSCTL_CREATE_USN_JOURNAL, // dwIoControlCode &cujd, // input buffer sizeof(cujd), // size of input buffer nullptr, // lpOutBuffer 0, // nOutBufferSize &br, // number of bytes returned nullptr) // OVERLAPPED structure ) { return true; } return false; }3. 获取USN日志信息 还是通过DeviceIoControl方法发送FSCTL_QUERY_USN_JOURNAL命令，获取当前卷USN日志的各项信息，检查USN日志是否获取成功。 FSCTL_QUERY_USN_JOURNAL - Win32 apps | Microsoft Docs inline bool volume::getUSNInfo() { DWORD br; if ( DeviceIoControl(hVol, // handle to volume FSCTL_QUERY_USN_JOURNAL, // dwIoControlCode nullptr, // lpInBuffer 0, // nInBufferSize &ujd, // output buffer sizeof(ujd), // size of output buffer &br, // number of bytes returned nullptr) // OVERLAPPED structure ) { return true; } return false; }4. 获取 USN Journal 文件的基本信息 仍然通过DeviceIoControl发送FSCTL_ENUM_USN_DATA遍历USN日志。 FSCTL_ENUM_USN_DATA - Win32 apps | Microsoft Docs bool volume::getUSNJournal() { MFT_ENUM_DATA med; med.StartFileReferenceNumber = 0; med.LowUsn = ujd.FirstUsn; med.HighUsn = ujd.NextUsn; // 根目录 CString tmp(_T("C:")); tmp.SetAt(0, vol); frnPfrnNameMap[0x20000000000005].filename = tmp; frnPfrnNameMap[0x20000000000005].pfrn = 0; constexpr auto BUF_LEN = 0x3900; // 尽可能地大，提高效率; CHAR Buffer[BUF_LEN]; DWORD usnDataSize; while (0 != DeviceIoControl(hVol, FSCTL_ENUM_USN_DATA, &med, sizeof(med), Buffer, BUF_LEN, &usnDataSize, nullptr)) { DWORD dwRetBytes = usnDataSize - sizeof(USN); // 找到第一个 USN 记录 auto UsnRecord = reinterpret_cast(static_cast(Buffer) + sizeof(USN)); while (dwRetBytes > 0) { // 获取到的信息 const CString CfileName(UsnRecord->FileName, UsnRecord->FileNameLength / 2); pfrnName.filename = CfileName; pfrnName.pfrn = UsnRecord->ParentFileReferenceNumber; frnPfrnNameMap[UsnRecord->FileReferenceNumber] = pfrnName; // 获取下一个记录 const auto recordLen = UsnRecord->RecordLength; dwRetBytes -= recordLen; UsnRecord = reinterpret_cast(reinterpret_cast(UsnRecord) + recordLen); } // 获取下一页数据 med.StartFileReferenceNumber = *reinterpret_cast(&Buffer); } return true; }这里我将获取到的信息放入了frnPfrnNameMap中 typedef struct _pfrn_name { DWORDLONG pfrn = 0; CString filename; } pfrn_name; typedef unordered_map Frn_Pfrn_Name_Map;这里不得不说USN日志文件的数据结构。 typedef struct { DWORD RecordLength; WORD MajorVersion; WORD MinorVersion; DWORDLONG FileReferenceNumber; DWORDLONG ParentFileReferenceNumber; USN Usn; LARGE_INTEGER TimeStamp; DWORD Reason; DWORD SourceInfo; DWORD SecurityId; DWORD FileAttributes; WORD FileNameLength; WORD FileNameOffset; WCHAR FileName[1]; } USN_RECORD_V2, *PUSN_RECORD_V2;这里我们需要用到FileReferenceNumber、ParentFileReferenceNumber、FileName。 USN日志在Windows中也有对应的命令，使用fsutil就可以创建日志 fsutil usn createJournal C: fsutil usn enumData 1 0 1 C:此时，可以看到USN日志的数据。
包含文件参照号，父文件参照号，以及文件名。 也就是上文提到的FileReferenceNumber、ParentFileReferenceNumber、FileName USN日志是一个树状结构，通过文件号和父文件号不断向上找，最终可以拼接出一个完整的路径。获得路径后即可存入数据库。 最后删除USN日志。 fsutil usn deleteJournal /D C:5. 删除USN日志文件 因为USN日志默认并不存在，所以在程序创建之后可以将它删除。 仍然是通过DeviceIoControl方法发送命令。 FSCTL_DELETE_USN_JOURNAL - Win32 apps | Microsoft Docs inline bool volume::deleteUSN() const { DELETE_USN_JOURNAL_DATA dujd; dujd.UsnJournalID = ujd.UsnJournalID; dujd.DeleteFlags = USN_DELETE_FLAG_DELETE; DWORD br; if (DeviceIoControl(hVol, FSCTL_DELETE_USN_JOURNAL, &dujd, sizeof(dujd), nullptr, 0, &br, nullptr) ) { CloseHandle(hVol); return true; } CloseHandle(hVol); return false; }6. 此时就可以通过遍历frnPfrnNameMap还原出每个文件的路径，并存入数据库 通过不断向上遍历查找，最后拼接出文件的路径。 inline void volume::getPath(DWORDLONG frn, CString& _path) { const auto end = frnPfrnNameMap.end(); while (true) { auto it = frnPfrnNameMap.find(frn); if (it == end) { _path = L":" + _path; return; } _path = _T("\\") + it->second.filename + _path; frn = it->second.pfrn; } } 此时，我们已经实现了实现Everything的第一步，建立数据库索引。 二、监控文件的变化监控文件的变化在这里我采用的是ReadDirectoryChangesW方法进行监控。ReadDirectoryChangesW function (winbase.h) - Win32 apps | Microsoft Docs 文件操作类型有四种，分别为 创建、更改、删除、重命名 对应到Windows API里是FILE_ACTION_ADDED、FILE_ACTION_MODIFIED、FILE_ACTION_REMOVED、FILE_ACTION_RENAMED_OLD_NAME。 通过监控这四个操作，我们可以实现监控文件的变化，并更新数据库索引。 void monitor_path(const char* path) { DWORD cb_bytes; char file_name[1000]; //设置文件名 char file_rename[1000]; //设置文件重命名后的名字; char _path[1000]; char notify[1024]; memset(_path, 0, 1000); strcpy_s(_path, 1000, path); WCHAR _dir[1000]; memset(_dir, 0, sizeof(_dir)); MultiByteToWideChar(CP_ACP, 0, _path, 1000, _dir, sizeof(_dir) / sizeof(_dir[0])); HANDLE dirHandle = CreateFile(_dir, GENERIC_READ | GENERIC_WRITE | FILE_LIST_DIRECTORY, FILE_SHARE_READ | FILE_SHARE_WRITE, nullptr, OPEN_EXISTING, FILE_FLAG_BACKUP_SEMANTICS, nullptr); if (dirHandle == INVALID_HANDLE_VALUE) //若网络重定向或目标文件系统不支持该操作，函数失败，同时调用GetLastError()返回ERROR_INVALID_FUNCTION { cout FileName, pnotify->FileNameLength / 2, file_name, 250, nullptr, nullptr); } //获取重命名的文件名; if (pnotify->NextEntryOffset != 0 && (pnotify->FileNameLength > 0 && pnotify->FileNameLength < 1000)) { auto p = reinterpret_cast(reinterpret_cast(pnotify) + pnotify-> NextEntryOffset); memset(file_rename, 0, 1000); memset(fileRename, 0, 1000); wcscpy_s(fileRename, pnotify->FileName); WideCharToMultiByte(CP_ACP, 0, p->FileName, p->FileNameLength / 2, file_rename, 250, nullptr, nullptr); } if (file_name[strlen(file_name) - 1] == '~') { file_name[strlen(file_name) - 1] = '\0'; } if (file_rename[strlen(file_rename) - 1] == '~') { file_rename[strlen(file_rename) - 1] = '\0'; } //设置类型过滤器,监听文件创建、更改、删除、重命名等; switch (pnotify->Action) { case FILE_ACTION_ADDED: if (strstr(file_name, "$RECYCLE.BIN") == nullptr) { string data; data.append(_path); data.append(file_name); #ifdef TEST cout |
【本文地址】